#include "junix.h"

void merge_sort1(int *l, int *r) {
	 ptrdiff_t dis = ptrdiff_t(r-l);
	if (dis<2) return;

	int *m=l+dis/2;
	merge_sort1(l,m);
	merge_sort1(m,r);
	std::inplace_merge(l,m,r);
}

template <typename Iterator>
void jmergesort(Iterator lhs, Iterator rhs) {
	typedef typename 
		std::iterator_traits<Iterator>::difference_type difference_type;
	difference_type dis=std::distance(lhs, rhs);

	if (dis<(difference_type(2)))
		return;

	Iterator mid = lhs+dis/2;
	jmergesort(lhs,mid);
	jmergesort(mid,rhs);
	std::inplace_merge(lhs,mid,rhs);
}


int main(int argc, char **argv)
{
	/*
	int v[]={5,6,7,8,9,0,1,2,3,4}; //10
	std::inplace_merge(v, v+5,v+10);
	std::ostream_iterator<int> oit(std::cout," ");
	copy(v, v+10, oit);
	std::cout<<"\n";
	*/

	const int sz =100000000;
	int *v2 =new int[sz];
	using boost::bind;
	using std::modulus;
	std::generate(v2,v2+sz,bind(modulus<int>(), bind(rand), sz));
	/*
	copy(v2,v2+sz,oit);
	std::cout<<"\n";
	*/

	jtime T;
	T.start();
	//merge_sort1(v2,v2+sz);
	jmergesort(v2,v2+sz);
	T.end();
	T.print();
	/*
	copy(v2,v2+sz,oit);
	std::cout<<"\n";
	*/
}
